public class BinarySearch {
    /*
    * 二分查找
    * 问题的关键在于边界值怎样处理和判断，本身的逻辑其实很朴实
    * 把握住区间不变，始终循环区间，当你的区间左端捅破了右端，那它就不再是区间了，循环自然就应该结束了
    * 所以，循环继续的条件是，范围仍然是个有意义的区间，即 min <= max
    * */

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        System.out.println(binarySearch.mySolution(new int[]{-1, 0, 3, 5, 9, 12}, -2));
    }

    // 我的想法
    public int mySolution(int[] nums, int target){
        int head = 0;
        int tail = nums.length-1;
        int index = (head + tail) / 2;

        // 最初的想法：while(index != head && index != tail)
        // 可以改进的地方： 当最后头尾只差1时，int做除法，最后只会获得较小的数，也就是，index不可能等于tail
        // 所以可以写作：while(index != head)
        while(index != head){
            if(target == nums[index])
                return index;

            if(target > nums[index]){
                head = index;
            } else{
                tail = index;
            }
            index = (head + tail) /2;
        }

        if(target == nums[head])
            return head;
        if(target == nums[tail])
            return tail;

        return -1;
    }

    // 题解写法
    public int solution(int[] nums, int target){
        /*
        提前检测，避免循环
        if(target > nums[nums.length-1] || target < nums[0])
            return -1;
        */
        int min = 0, max = nums.length-1, mid;
        while(min<=max){
            mid = (min + max) / 2;
            if (target == nums[mid])
                return mid;
            else if (target > nums[mid])
                min = mid + 1;
            else
                max = mid -1;
        }
        return -1;
    }
}
